package letcode.problem.dynamicProgra;

/*
 *https://leetcode.cn/problems/min-cost-climbing-stairs/description/?envType=study-plan-v2&envId=dynamic-programming
 * **/
public class MinCostClimbStairs {
    /**
     * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * <p>
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * <p>
     * 请你计算并返回达到楼梯顶部的最低花费。
     */

    public static int minCostClimbingStairs(int[] cost) {
        //fn = min(fn-1, fn-2 + cost[i])
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;

    }

    public static void main(String[] args) {
        int[] costs = new int[]{10,15,20};
        System.out.println(minCostClimbingStairs(costs));
    }
}
